#include <iostream>
#include <vector>
#include <stdio.h>

template<typename T>
void do_quick_sort(std::vector<T>& array, int left, int right) {
    int l = left, r = right, p = left;
    if (right <= left) return;

    auto swap = [&array](int a, int b) {
        T temp = array[a]; 
        array[a] = array[b],
        array[b] = temp;
    };
    while (l < r) {
        while (l < r && array[r] >= array[p]) r--;
        while (l < r && array[l] <= array[p]) l++;
        swap(l, r);
    }
    swap(p, l);
    do_quick_sort(array, left, l-1);
    do_quick_sort(array, l+1, right);
}

template<typename T>
void sort(std::vector<T>& array) {
    do_quick_sort(array, 0, array.size()-1);    
    for (T e: array)
        std::cout << e << ",";
    std::cout << std::endl;
}

template<typename T>
int do_binarySearch(std::vector<T>& sorted_arr, T target, size_t left, size_t right) {
    size_t mid = left + (right - left) / 2;

    if (right < left) return -1;
    if (target == sorted_arr[mid])
        return mid;
    else if (target < sorted_arr[mid])
        return do_binarySearch(sorted_arr, target, left, mid-1);
    else
        return do_binarySearch(sorted_arr, target, mid+1, right);
}

template<typename T>
int binarySearch(std::vector<T>& arr, T target) {
    sort(arr);
    return do_binarySearch(arr, target, 0, arr.size()-1); 
}

int main(void)
{
    printf("二分查找\n\n");
    std::vector<int> arr = {8,8,7, 8,6,7,5,6,4,3,2,1};
    int target = 4;
    int idx = binarySearch(arr, target);
    
    printf("target %d, index %d\n", target, idx);
    return 0;
}